package Java0411;

class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

public class Solution {

    // 相交链表
    // 编写一个程序，找到两个单链表相交的起始节点。
    // 如果两个链表没有交点，返回 null.
    // 在返回结果后，两个链表仍须保持原有的结构。
    // 可假定整个链表结构中没有循环。
    // 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int lengthA = length(headA);
        int lengthB = length(headB);
        boolean flag = lengthA > lengthB;
        int steps = flag ? lengthA - lengthB : lengthB - lengthA;
//        if (steps > lengthA || steps > lengthB) {
//            return null;
//        }
        ListNode curA = headA;
        ListNode curB = headB;
        if (flag == true) {
            for (int i = 0; i < steps; i++) {
                curA = curA.next;
            }
        }else {
            for (int i = 0; i < steps; i++) {
                curB = curB.next;
            }
        }
        while (true) {
            if (curA == null || curB == null) {
                return null;
            }
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
    }

    private int length(ListNode head) {
        ListNode cur = head;
        int length = 0;
        for (; cur != null; cur = cur.next) {
            length++;
        }
        return length;
    }
}
